// 2 5 8 9 7 4 6 11
// 最长的子序列是多少个 长度

// 贪心算法

// 我们找序列中最有潜力的那一个，比最后一个大的，直接放到队列中，如果比最后一个小
// 则将它替换到队伍中比他第一个大的那一项（二分查找）

// 2 3  （更有潜力）
// 2 5


// 贪心算法+二分查找+追溯


// 2 （2的前一个是null）
// 2 5 （5的前一个是2）
// 2 5 8 （8的前一个是5）
// 2 5 8 9 （9的前一个是8）
// 2 5 8 9 7  （❌7无法放到9后边）
// 2 5 7 9 （7去找比自己大的那一项替换，虽然错误，但我们找的是后面更有潜力的。序列长度是不会错的，7的前一个是5）
// 2 5 7 9 11 （11的前一个是9）

// 追溯
// 2 5 8 9 11  = 5
function getSeq(arr) {
    debugger
    let result = [0]
    const len = arr.length // 总长度
    let resultLastIndex
    let start
    let end
    let middle = 0
    let p = arr.slice(0).fill(0)
    for (let i = 0; i < len; i++) {
        const arrI = arr[i]
        if (arrI != 0) {
            // 获取队列中的最后一项
            resultLastIndex = result[result.length - 1]
            if (arr[resultLastIndex] < arrI) {
                result.push(i)
                p[i] = resultLastIndex
                continue
            }
            // ..替换
            start = 0
            end = result.length - 1
            while (start < end) { // 折半 查找
                middle = Math.floor((start + end) / 2)
                // 中间那一项的值
                // 1,2,3,4,6    5
                if (arr[result[middle]] < arrI) {
                    start = middle + 1
                } else {
                    end = middle
                }
            }
            if (arrI < arr[result[end]]) {
                p[i] = result[end - 1]
                result[end] = i // 发现最后找到的索引比这一项大，那就用这个索引换掉，因为更有潜力
            }
        }
    }
    let i = result.length
    let last = result[i - 1]
    while (i-- > 0) {
        result[i] = last
        last = p[last]
    }
    return result
}


// console.log(getSeq([1, 2, 3, 4, 5, 0]))
console.log(getSeq([2, 3, 1, 5, 9, 4]))
